package com.c2b.algorithm.newcoder;

/**
 * <a href='https://www.nowcoder.com/practice/d3df40bd23594118b57554129cadf47b?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj'>二分查找-I </a>
 *
 * @author c2b
 * @since 2024/3/14 13:23
 */
public class BM17Search {
    public static class Solution {
        public int search(int[] nums, int target) {
            if (nums.length == 0) {
                return -1;
            }
            // 当 target 小于nums[0] 或者 target 大于nums[nums.length - 1]，一定不存在
            if (target < nums[0] || target > nums[nums.length - 1]) {
                return -1;
            }
            int leftIndex = 0;
            int rightIndex = nums.length - 1;
            int mid;
            while (leftIndex <= rightIndex) {
                // 求中点，避免越界
                mid = rightIndex - ((rightIndex - leftIndex) >> 1);
                if (nums[mid] == target) {
                    return mid;
                }
                if (nums[mid] < target) {
                    leftIndex = mid + 1;
                } else {
                    rightIndex = mid - 1;
                }
            }
            return -1;
        }
    }
}
